package com.changanw.code33;

/**
 * @author changanw
 * @description  //二分法查找数组中的位置
 * @date 2023/7/28 16:29
 */
public class Code33 {
  public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length -1;
    while(left <= right){
      int mid = left + (right - left)/2;
      if(target == nums[mid]){
        return mid;
      }
      if(nums[mid] >= nums[left]){
        //target 落在 left 和 mid 之间，则移动我们的right，完全有序的一个区间内查找
        if (nums[mid] > target && target >= nums[left]) {
          right = mid - 1;
          // target 落在right和 mid 之间，有可能在数组1， 也有可能在数组2
        } else if (target > nums[mid] || target < nums[left]) {
          left = mid + 1;
        }
      }else if (nums[mid] < nums[left]) {
        //有序的一段区间，target 在 mid 和 right 之间
        if (nums[mid] < target && target <= nums[right]) {
          left = mid + 1;
          // 两种情况，target 在left 和 mid 之间
        } else if (target < nums[mid] || target > nums[right]) {
          right = mid - 1;
        }
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    Code33 code33 = new Code33();
    int nums[] = {4,5,6,7,0,1,2};
    code33.search(nums,2);
  }
}
